package LearnDataStructure.c_树结构.例题;

import LearnDataStructure.c_树结构.BSTNode;
import LearnDataStructure.c_树结构.有序树.二叉树.b_MyBinaryTreebyLinked;
/**
 * @version: 1.0
 * @Author: wuqiu
 * @date: 2023-07-12 21:42
 * @description: LeetcodeLearnAlgorithm -> LearnDataStructure.c_树结构.例题
 */
public class g_求BST某节点后继可利用parent {
    public static void main(String[] args) {
        g_求BST某节点后继可利用parent test = new g_求BST某节点后继可利用parent();
        b_MyBinaryTreebyLinked<Integer,Integer> binaryTree = new b_MyBinaryTreebyLinked<>();
        binaryTree.insert(6,6);
        BSTNode<Integer, Integer> node1 = binaryTree.insert(7, 7);
        binaryTree.insert(4,4);
        binaryTree.insert(5,5);
        BSTNode<Integer, Integer> node = binaryTree.insert(8, 8);
        binaryTree.insert(2,2);

        BSTNode<Integer, Integer> successor = test.successor0(node1);
        System.out.println(successor);

        System.out.println(binaryTree);
    }

    public BSTNode<Integer,Integer> successor0(BSTNode<Integer,Integer> node) {
        if (node == null) {
            return null;
        }
        if (node.right != null) {
            BSTNode<Integer, Integer> current = node.right;
            while (current.left != null) {
                current = current.left;
            }
            return current;
        }
        BSTNode<Integer, Integer> p = node.parent;
        while (p != null && !node.isLeftChild) {
            node = p;
            p = p.parent;
        }
        return p;
    }
}
